#include "main/utils.h"
using namespace std;

bool reconstruction(const vector<int> org, const vector<vector<int>>& seqs) {
  map<int, set<int>> graph;
  map<int, int> in_degrees;
  for (auto seq : seqs) {
    for (auto num : seq) {
      if (num < 1 || num > org.size())
        return false;
      in_degrees[num] = 0;
    }
  }
  for (int i = 0; i < seqs.size(); ++i) {
    for (int j = 1; j < seqs[i].size(); ++j) {
      int pre = seqs[i][j - 1];
      int post = seqs[i][j];
      if (graph[pre].find(post) == graph[pre].end()) {
        graph[pre].insert(post);
        ++in_degrees[post];
      }
    }
  }

  queue<int> queue;
  for (auto num : in_degrees) {
    if (num.second == 0) {
      queue.push(num.first);
    }
  }

  vector<int> new_seq;
  while (queue.size() == 1) {
    auto cur = queue.front();
    queue.pop();
    new_seq.push_back(cur);
    for (auto next : graph[cur]) {
      --in_degrees[next];
      if (in_degrees[next] == 0) {
        queue.push(next);
      }
    }
  }

  if (new_seq.size() != in_degrees.size() ||
      new_seq.size() != org.size()) {
    return false;
  }
  for (int i = 0; i < new_seq.size(); ++i) {
    if (new_seq[i] != org[i]) {
      return false;
    }
  }
  return true;
}

int main() {
  vector<int> org = {4, 1, 5, 2, 6, 3};
  vector<vector<int>> seqs = {{5, 2, 6, 3}, {4, 1, 5, 2}};
  cout << reconstruction(org, seqs) << endl;

  org = {1, 2, 3};
  seqs = {{1, 2}, {1, 3}};
  cout << reconstruction(org, seqs) << endl;

  return 0;
}
